package com.datastructure.test.rearrangestring;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class RearRangeString {

    public static void main(String[] args) {
        RearRangeString rearRangeString = new RearRangeString();
        String string = rearRangeString.rearrangestring("nowcoder");
        System.out.println(string);
    }

    public String rearrangestring (String str) {
        // write code here
        int cnt[] = new int[128];
        for(char c : str.toCharArray()){
            cnt[c]++;
        }
        PriorityQueue<Character> characters = new PriorityQueue<>((a, b) -> cnt[b] - cnt[a]);
        for(char i = 'a'; i <= 'z'; i++){
            if(cnt[i] == 0) continue;
            characters.offer(i);
        }
        StringBuilder builder = new StringBuilder();
        while(characters.size() > 1){
            char first = characters.poll();
            char second = characters.poll();
            builder.append(first);
            builder.append(second);
            if (--cnt[first] > 0) characters.offer(first);
            if (--cnt[second] > 0) characters.offer(second);
        }
        if (characters.size() == 1) builder.append(characters.poll());
        if (builder.length() < str.length()) return "";
        return builder.toString();
    }
}
